package com.cango.student.algorithm.sort;


/**
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(n2) 	O(n2)	O(n2)	O(1) 不稳定	简单
 */
public class SelectionSort {

    /**
     * 选择排序
     * 大循环 i <循环总次数
     * 小循环  k=i+1
     * 在内层循环结束，也就是找到本轮循环的最小的数以后，与第一个再进行交换
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {99, 54, 40, 20, 30, 9, 8, 6, 4, 1};
        // 选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
            // i是当前要替换的位子
            int k = i; // k是最小值的位置
            for(int j = k + 1; j < arr.length; j++){// 选最小的记录
                if(arr[j] < arr[k]){
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            // 在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }

        System.out.println();
        System.out.println("交换后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
